package util;

/**
 * @Classname TreeNode
 * @Description kektree node
 * @Date
 * @Created by kevin
 */
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import it.unisa.dia.gas.jpbc.Element;
import it.unisa.dia.gas.jpbc.Pairing;
import it.unisa.dia.gas.plaf.jpbc.pairing.PairingFactory;
public class TreeUtil {
    /**
     * 返回树中节点个数
     * @param root
     * @return
     */
    public static int getTreeNodeNum(TreeNode root){
        if(root.getLeftChild()==null && root.getRightChild()==null){
            return 1;
        }
        return getTreeNodeNum(root.getLeftChild())+
                getTreeNodeNum(root.getRightChild())+1;
    }
    /**
     * 返回叶子节点到树根的路径
     * @param leaf
     * @return
     */
    public static List<TreeNode> getPath(TreeNode leaf){
        if(leaf==null){
            return null;
        }
        List<TreeNode> pathNodeList=new ArrayList<TreeNode>();
        TreeNode TempNode=leaf;
        while(TempNode.getParent()!=null){
            pathNodeList.add(TempNode);
            TempNode=TempNode.getParent();
        }
        pathNodeList.add(TempNode);
        return pathNodeList;
    }
    /**
     * 获得最小覆盖集
     * @param T
     * @param reList
     * @return
     */
    public static Set<TreeNode> KUNNodes(List<TreeNode> T,List<TreeNode> reList){
        Set<TreeNode> X=new HashSet<TreeNode>();
        Set<TreeNode> Y=new HashSet<TreeNode>();
        for (TreeNode treeNode : reList) {
            X.addAll(getPath(treeNode));
        }
        for (TreeNode treeNode : X) {
            if(treeNode.getLeftChild()!=null && !X.contains(treeNode.getLeftChild())){
                Y.add(treeNode.getLeftChild());
            }
            if(treeNode.getRightChild()!=null && !X.contains(treeNode.getRightChild())){
                Y.add(treeNode.getRightChild());
            }
        }
        if(Y.isEmpty())
            Y.add(T.get(1));
        return Y;
    }
    /**
     * 创建包含n个叶子节点的树
     * @param n
     * @return
     */
    public static List<TreeNode> createTree(int n){

        List<TreeNode> nodeList=new ArrayList<TreeNode>();
        Pairing pairing = PairingFactory.getPairing("a.properties");
        Element Ski = pairing.getZr().newRandomElement().getImmutable();
        nodeList.add(new TreeNode("node"+0,Ski));//node0为占位节点
        int depth=(int)(Math.log(n)/Math.log(2))+1;
        for(int i=1;i<=depth;i++){
            for(int j=(int)(Math.pow(2, i-1));j<(int)(Math.pow(2, i));j++){
                Element Ski2 = pairing.getZr().newRandomElement().getImmutable();
                nodeList.add(new TreeNode("node"+j,Ski2));
                nodeList.get(j).isLeaf=false;
                if(i==depth){
                    nodeList.get(j).isLeaf=true;
                }
            }
        }
        for(int i=1;i<nodeList.size();i++){
            if(i!=1)
                nodeList.get(i).setParent(nodeList.get(i/2));
            if(!nodeList.get(i).isLeaf){
                nodeList.get(i).setLeftChild(nodeList.get(2*i));
                nodeList.get(i).setRightChild(nodeList.get(2*i+1));
            }
        }
        return nodeList;
    }
}
